package cn.xiaolang.function.data_structure;

import java.util.Arrays;

/**
 * 加一
 * <p>
 * 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
 * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
 * 你可以假设除了整数 0 之外，这个整数不会以零开头。
 * </p>
 * 示例 1:
 * <p>
 * 输入: [1,2,3]
 * 输出: [1,2,4]
 * 解释: 输入数组表示数字 123。
 *
 * @author fuhw/Dean
 * @date 2020-03-26
 */
public class ArrayPlusOne {

    public static void main(String[] args) {
        int[] nums = {9, 7, 7};
        System.out.println(Arrays.toString(plusOne(nums)));
    }

    /**
     * 思路:
     * 1 一位一位运算
     * 2 余10（%10）取余位，模10（/10）取进位
     * 3 最后一位进位，扩展数组
     *
     * @param nums 指定数组
     * @return 返回数组的中心索引
     */
    public static int[] plusOne(int[] nums) {
        // 加进位
        int carry = 1;

        // O(n)
        for (int i = nums.length - 1; i >= 0; i--) {
            if (carry == 0) {
                return nums;
            }
            int bitPlus = nums[i] + carry;
            carry = bitPlus / 10;
            nums[i] = bitPlus % 10;
        }

        if (carry != 0) {
            int[] result = new int[nums.length + 1];
            result[0] = 1;
            return result;
        }
        return nums;
    }
}
